import random

def split_public(public):
    """
    Split Public Key into Components
    """
    y = public[:16]
    g = public[16:32]
    p = public[32:]
    return y, g, p

def choose_k(p):
    """
    Choose k relatively-prime to p-1
    """
    p = int(p, 2)
    k = random.randint(3, p-2)
    while not _is_relative_prime(p-1, k):
        k = random.randint(3, p-2)
    return _dec_to_bin(k)

def calculate_a(g, k, p):
    """
    Calculate part a of ciphertext
    """
    g = int(g, 2)
    k = int(k, 2)
    p = int(p, 2)
    a = (g**k) % p
    return _dec_to_bin(a)

def calculate_b(y, k, m, p):
    """
    Calculate part b of ciphertext
    """
    y = int(y, 2)
    k = int(k, 2)
    m = int(m, 2)
    p = int(p, 2)
    b = ((y**k % p) * m) % p
    return _dec_to_bin(b)

def produce_ciphertext(a, b):
    """
    Produce final ciphertext (concatenation of a and b)
    """
    return a + b

def _is_relative_prime(x, y):
    """
    Check if x and y are relatively-prime.
    Adapted from the gcd algorithm on page 245 of Bruce Schneier's
    Applied Cryptography, Second Edition.
    """
    g = y
    while x > 0:
        g = x
        x = y % x
        y = g
    return g == 1

def _dec_to_bin(decimal):
    binary_reps = {'0': '000',
                   '1': '001',
                   '2': '010',
                   '3': '011',
                   '4': '100',
                   '5': '101',
                   '6': '110',
                   '7': '111'
    }
    oct_rep = str(oct(decimal))
    binary_string = ""
    for c in oct_rep:
        if c != "L":
            binary_string += binary_reps[c]
    if len(binary_string) > 16:
        binary_string = binary_string[len(binary_string) - 16:]
    while len(binary_string) < 16:
        binary_string = "0" + binary_string
    return binary_string